//图像平滑器 是大小为 3 x 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。 
//
// 每个单元格的 平均灰度 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。 
//
// 如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。 
//
// 
//
// 给你一个表示图像灰度的 m x n 整数矩阵 img ，返回对图像的每个单元格平滑处理后的图像 。 
//
// 
//
// 示例 1: 
//
// 
//
// 
//输入:img = [[1,1,1],[1,0,1],[1,1,1]]
//输出:[[0, 0, 0],[0, 0, 0], [0, 0, 0]]
//解释:
//对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
//对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
//对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0
// 
//
// 示例 2: 
//
// 
//输入: img = [[100,200,100],[200,50,200],[100,200,100]]
//输出: [[137,141,137],[141,138,141],[137,141,137]]
//解释:
//对于点 (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137
//
//对于点 (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.
//666667) = 141
//对于点 (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) =
// 138
// 
//
// 
//
// 提示: 
//
// 
// m == img.length 
// n == img[i].length 
// 1 <= m, n <= 200 
// 0 <= img[i][j] <= 255 
// 
// Related Topics 数组 矩阵 👍 115 👎 0

package leetcode.editor.cn;

public class _661_ImageSmoother {
    public static void main(String[] args) {
        Solution solution = new _661_ImageSmoother().new Solution();
//        int[][] img = new int[][] {{100,200,100}, {200,50,200}, {100,200,100}};
        int[][] img = new int[][] {{1,2,3}, {4,5,6}, {7,8,9}};
//        int[][] img = new int[][]{{1}};
        int[][] res = solution.imageSmoother(img);
        show(res);
    }

    private static void show(int[][] res) {
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[i].length; j++) {
                System.out.print(res[i][j] + "\t");
            }
            System.out.println();
        }
    }

    // 前缀和
    class Solution {
        public int[][] imageSmoother(int[][] img) {
            int m = img.length;
            int n = img[0].length;
            int[][] sum = new int[m + 2][n + 2];
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
//                    if (i == m + 1) {
//                        sum[i][j] = sum[i - 1][j];
//                    } else if (j == n + 1) {
//                        sum[i][j] = sum[i][j - 1];
//                    } else {
//                        sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1];
//                    }
                    sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + img[i - 1][j - 1];
                }
            }

            int[][] res = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int a = Math.max(0, i - 1);
                    int b = Math.max(0, j - 1);
                    int c = Math.min(m - 1, i + 1);
                    int d = Math.min(n - 1, j + 1);

                    int cnt = (c - a + 1) * (d - b + 1);
                    int num = sum[c + 1][d + 1] - sum[c + 1][b] - sum[a][d + 1] + sum[a][b];
                    res[i][j] = num / cnt;
                }
            }
            return res;
        }
    }


    class Solution2 {
        public int[][] imageSmoother(int[][] img) {
            int m = img.length;
            int n = img[0].length;
            int[][] res = new int[m][n];

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int sum = 0;
                    int num = 0;
                    for (int x = i - 1; x <= i + 1; x++) {
                        for (int y = j - 1; y <= j + 1; y++) {
                            if (x >= 0 && x < m && y >= 0 && y < n) {
                                sum += img[x][y];
                                num++;
                            }
                        }
                    }
                    res[i][j] = sum / num;
                }
            }
            return res;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    // 自己是个垃圾
    class Solution1 {
        public int[][] imageSmoother(int[][] img) {
            int[][] res = new int[img.length][img[0].length];
            for (int i = 0; i < res.length; i++) {
                for (int j = 0; j < res[0].length; j++) {
                    res[i][j] = getAvg(img, i, j);
                }
            }

            return res;
        }

        private int getAvg(int[][] img, int indexI, int indexJ) {
            int m = img.length;
            int n = img[0].length;
            int sum = 0;
            int num = 0;

            if (m == 1 && n == 1) {
                return img[0][0];
            }


            if (m > 2 && n > 2) {
                if (indexI == 0 && indexJ == 0) {
                    sum = img[indexI][indexJ] + img[indexI + 1][indexJ] + img[indexI][indexJ + 1] + img[indexI + 1][indexJ + 1];
                    num = 4;
                } else if (indexI == 0 && indexJ == n - 1) {
                    sum = img[indexI][indexJ] + img[indexI][indexJ - 1] + img[indexI + 1][indexJ] + img[indexI + 1][indexJ - 1];
                    num = 4;
                } else if (indexI == m - 1 && indexJ == 0) {
                    sum = img[indexI][indexJ] + img[indexI - 1][indexJ] + img[indexI][indexJ + 1] + img[indexI - 1][indexJ + 1];
                    num = 4;
                } else if (indexI == m - 1 && indexJ == n - 1) {
                    sum = img[indexI][indexJ] + img[indexI - 1][indexJ] + img[indexI][indexJ - 1] + img[indexI - 1][indexJ - 1];
                    num = 4;
                } else if (indexI == 0) {
                    sum = img[indexI][indexJ] + img[indexI][indexJ - 1] + img[indexI][indexJ + 1] +
                            img[indexI + 1][indexJ] + img[indexI + 1][indexJ - 1] + img[indexI + 1][indexJ + 1];
                    num = 6;
                } else if (indexI == m - 1) {
                    sum = img[indexI][indexJ] + img[indexI][indexJ - 1] + img[indexI][indexJ + 1] +
                            img[indexI - 1][indexJ] + img[indexI - 1][indexJ - 1] + img[indexI - 1][indexJ + 1];
                    num = 6;
                } else if (indexJ == 0) {
                    sum = img[indexI][indexJ] + img[indexI - 1][indexJ] + img[indexI + 1][indexJ] +
                            img[indexI][indexJ + 1] + img[indexI - 1][indexJ + 1] + img[indexI + 1][indexJ + 1];
                    num = 6;
                } else if (indexJ == n - 1) {
                    sum = img[indexI][indexJ] + img[indexI - 1][indexJ] + img[indexI + 1][indexJ] +
                            img[indexI][indexJ - 1] + img[indexI - 1][indexJ - 1] + img[indexI + 1][indexJ - 1];
                    num = 6;
                } else {
                    sum = img[indexI - 1][indexJ - 1] + img[indexI][indexJ - 1] + img[indexI + 1][indexJ - 1] +
                            img[indexI - 1][indexJ] + img[indexI][indexJ] + img[indexI + 1][indexJ] +
                            img[indexI - 1][indexJ + 1] + img[indexI][indexJ + 1] + img[indexI + 1][indexJ + 1];
                    num = 9;
                }

                return sum / num;
            }
            return 0;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}